本场链接:Codeforces Round #581 Div2

闲话

速度很拉胯,不够写D的.赛后发现比赛场上想写出D还是有点差距感觉.

A. BowWow and the Timetable

原题大意:给你一个整数,问比他严格小的形如$4^k$的数的个数.原数非常大,输入为原数的二进制表示的字符串.
数据范围:
$0 \leq s \leq 2^{100}$

思路

一个比较好想到的点是$4$无非就是两个$2$,答案还要算上$0$,所以就是长度$n$的前提下,$n/2$.如果除了第一位之外全是$0$,这个是对的,因为本身表示的那个数取不到,他得是严格大于,如果有一个,就可以取到.因此还要加一个判断看是不是后面完全都是$0$的.到这里其实还差一点,因为之前的分析的的前提是这个数可以表示成一个$4$的幂的形式,但是如果$2$的指数是一个奇数,就不能表示了.因此只有偶数次幂的时候,有那个看是否全是$0$的判断,否则就没有.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	string s;cin >> s;
	int n = s.size();
	int ok = 0;
	for(int i = 1;i < n;++i)
		if(s[i] != '0')
			ok = 1;
	printf("%lld\n",n / 2 + (n % 2 == 1 ? ok : 0));
    return 0;
}

B. Mislove Has Lost an Array

原题大意:构造一个长度为$n$的序列,要求里面不同的元素的个数在$[l,r]$之间.并且每个元素要么是$1$,要么是一个偶数,对于一个偶数的元素$a_i$,必须保证$a_i/2$是存在于这个序列里的.问这个序列最小和最大的总和分别是多少.
数据范围:
$1 \leq n \leq 1000$
$1 \leq l \leq r \leq min(n,20)$

思路

由于这个题目的条件特别的强,导致了每个元素其实都是$2$的幂,所以可以从这个方向下手.又要保证说整个序列里不同的元素数量要在一个区间内,而这个区间的长度很小,所以可以枚举区间里的每一个数,直接遍历.假设当前要算的结果的是整个序列里有$i$个不同元素的,那么最小的时候,就是尽量塞$1$进去,但是又要满足不同数量,所以完全可以只搞出$i$个幂,就是$1,2,4,...2^i$这一段,剩下的全部填$1$,这样就最小了,最大的也是同理,只要让后面的全部填$2^i$就可以了.最后全套一遍就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qmul(ll a, ll b) 
{
  	ll L = a * (b >> 25LL)  * (1LL << 25) ;
  	ll R = a * (b & ((1LL << 25) - 1)) ;
  	return (L + R);
}
ll qpow(ll a,ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1)	res = qmul(res,a);
		a = qmul(a,a);
		b >>= 1;
	}
	return res;
}
int main()
{
	int n,l,r;cin >> n >> l >> r;
	ll minv = qpow(2,l) - 1 + n - l;
	ll maxv = qpow(2,r) - 1 + (n - r) * qpow(2,r - 1);
	for(int i = l;i <= r;++i)
	{
		ll A = qpow(2,i) - 1 + n - i,B = qpow(2,i) - 1 + (n - i) * qpow(2,i - 1);
		minv = min({minv,A,B});
		maxv = max({maxv,A,B});
	}

	cout << minv << " " << maxv << endl;
    return 0;
}

C. Anna, Svyatoslav and Maps

原题大意:没法翻译,自行看题.

数据范围:
$2 \leq n \leq 100$

思路

定义关键点:一个关键点是线路上最短路必经的点,也就是序列里不会被删掉的点,显然$p_1,p_m$是关键点.顺序考虑每个点,如果当前这个$p_i$是一个关键点的话,意味着从上一个关键点走到$p_{i+1}$是必须要经过$p_i$的,才会保留这个$p_i$.设上一个关键点是$u$,必须要经过的条件就是$u->p_i$的距离不等于$p_i->p_{i+1}$的距离减掉$1$.一旦删掉,这条路就会被一个最短路的点替代掉.所以做法已经非常显然了,就是跑一个$floyd$求出任意两点距离,再按照从前往后的顺序遍历找到所有的关键点就可以了,

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105,M = 1e6+7;
char _g[N][N];
int g[N][N],f[N][N];
int p[M];
int main()
{
	int n;scanf("%d",&n);
	for(int i = 1;i <= n;++i)	scanf("%s",_g[i] + 1);
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
			f[i][j] = int(_g[i][j] - '0');
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j)
			if(!f[i][j])
				f[i][j] = 0x3f3f3f3f;
		f[i][i] = 0;
	}
		
	//floyd
	for(int k = 1;k <= n;++k)
		for(int i = 1;i <= n;++i)
			for(int j = 1;j <= n;++j)
				f[i][j] = min(f[i][j],f[i][k] + f[k][j]);
				
	int m;scanf("%d",&m);
	for(int i = 1;i <= m;++i)	scanf("%d",&p[i]);
	vector<int> res;
	int last = p[1],pos = 1;res.push_back(last);
	for(int i = 2;i <= m - 1;++i)
	{
		if(f[last][p[i]] != f[last][p[i + 1]] - 1)
		{
			last = p[i];
			pos = i;
			res.push_back(p[i]);
		}
	}
	res.push_back(p[m]);
	printf("%d\n",(int)res.size());
	for(auto& v : res)	printf("%d ",v);
    return 0;
}

D. Kirk and a Binary String

原题大意:给一个二进制字符串s,构造一个等长的字符串t,保证任意两个区间内的子串的最长不降子序列的长度相等.并且t里的0尽量多.
数据范围:
$1 \leq |S| \leq 2000$ (easy)
$1 \leq |S| \leq 10^5$

思路

可以想到这样一个性质:对于一个0变成一个1是毫无意义的,不会让答案变得更好,甚至可能破坏性质.整个过程应该只有1变成0.那么整个序列的最长不降序列的长度记作$len$,$0$的个数记为$cnt$,那么整个序列里应该有$len-cnt$个1可以换成0.如果恰好相等则说明没有1可以换了,就是原串.因为最好情况就是整个不降序列就是一个纯0串.所以两者之差就是可以转换的数了.
考虑怎样的一个1可以被替换掉:如果以他为结尾的最长不降序列的长度恰好是应该修改的个数的话,就说明他是应该修改的最后一个数,因此可以从后往前依次看每个$1$是否满足这个性质,并修改掉当前还需要修改几个数.其次,还要做一个$dp$求出以1结尾的最长不降子序列的长度,分析到此整个题就比较容易了.

代码

using namespace std;
typedef long long ll;

const int N = 1e5+7;
char s[N];
int f[N],sum[N];
int main()
{
	scanf("%s",s + 1);
	int n =	strlen(s + 1);
	f[0] = 1;
	int cnt = 0;
	for(int i = 1;i <= n;++i)
	{
		f[i] = f[i - 1];sum[i] = sum[i - 1];
		if(s[i] == '1')	f[i] = max(f[i - 1] + 1,sum[i - 1] + 1);
		else	sum[i] = sum[i - 1] + 1,++cnt;
	}
	int len = f[n] - cnt,c = 0;
	for(int i = n;i >= 1;--i)
	{
		if(s[i] == '1' && f[i] == sum[i] + len - c)
		{
			++c;
			s[i] = '0';
		}
	}
	printf("%s",s + 1);
    return 0;
}